Let G = (V (G), E(G)) be a simple, finite and undirected graph of order n. A k-vertex weighting of a graph G is a mapping w: V (G) → {1, . . ., k}. A k-vertex weighting induces an Edge labeling fw: E(G) → N such that fw(uv) = w(u) + w(v). Such a labeling is called an Edge-coloring k-vertex weighting if fw(e) ̸ = fw(e′ ) for any two adjacent Edges e and e′ . Denote by μ ′ (G) the minimum k for G to admit an Edge-coloring k-vertex weighting. In this paper, we determine μ ′ (G) for some classes of graphs.

Let G be a graph and c′ aa(G) denotes the minimum number of colors required for an acyclic Edge coloring of G in which no two adjacent vertices are incident to Edges colored with the same set of colors. We prove a general bound for c′ aa (G □ H) for any two graphs G and H. We also determine exact value of this parameter for the Cartesian product of two paths, Cartesian product of a path and a cycle, Cartesian product of two trees, hypercubes. We show that c′ aa (Cm □ Cn) is at most 6 fo every m ≥ 3 and n≥3. Moreover in some cases we find the exact value of c′ aa (Cm □ Cn).

A labeling of the Edges of a graph is called vertex-coloring if the labeled degrees of the vertices yield a proper coloring of the graph. In this paper, we show that such a labeling is possible from the label set 1, 2, 3 for the complete graph Kn, n≥3.

Strong Edge-coloring of a graph is a proper Edge coloring such that every Edge ofa path of length 3 uses three different colors. The strong chromatic index of a graphis the minimum number k such that there is a strong Edge-coloring using k colors andis denoted by χ_s^'(G). We give efficient algorithms for strong Edge-coloring of certainnanosheets using optimum number of colors.

Please click on PDF to view the abstract.